1. Field of the Invention
The invention relates to routing multicast packets.
2. Related Art
In a network of networks, sometimes called an xe2x80x9cinternetxe2x80x9d (alternatively, an xe2x80x9cinternetxe2x80x9d), routers are typically separated into a set of routing domains (alternatively, xe2x80x9cautonomous routing groupsxe2x80x9d or xe2x80x9cdomainsxe2x80x9d). Routers in each routing domain maintain information about destinations and associated xe2x80x9cnext hopsxe2x80x9d to those destinations; the routers are able to maintain such information by exchanging routing protocol messages.
Such networks can include systems for transmitting packets which are unicast (directed to a single destination device) or multicast (directed to multiple destination devices). When packets are multicast, they are transmitted using a multicast distribution tree. Accordingly, when a router forwards a multicast packet, the router must maintain routing information about its communication interface to the next hop toward the root of the multicast distribution tree, and for all successive next hops leading to the multiple destination devices.
One problem which has arisen in the art is that a large amount of information must therefore be recorded for routing multicast packets; this problem is made worse with increasing size of the internet.
Accordingly, it would be desirable to provide a method and system for routing multicast packets in an internet, in which not all routers in a routing domain would be required to maintain complete routing information for roots of multicast trees, if those roots are external to the routing domain. This advantage is achieved in an embodiment of the invention in which only selected routers in a routing domain maintain routing information about those roots which are external to the routing domain, while all other routers in the routing domain maintain only routing information about those roots which are internal to the routing domain.
The invention provides a method and system for multicast packet routing, in which only selected routers in a network subset (in a preferred embodiment, those routers on the border of the network subset) maintain routing information about roots of multicast trees for roots which are external to the network subset, while all other routers in the network subset (non-border routers), maintain only information regarding routing within the network subset, including routing to border routers of the network subset, but not including routing to roots which are external to the network subset. The network subset is preferably a routing domain or other autonomous routing group.
In a preferred embodiment, a multicast distribution tree is maintained, using protocol messages which are transmitted from leaf nodes toward a root of the tree, while data packets to be multicast are distributed from the root toward the leaf nodes. In each network subset, such as a routing domain or other autonomous system, each multicast packet is associated with a multicast distribution tree. A subtree of the multicast distribution tree within a single routing domain is associated with an upstream border router (UBR) and a set of downstream border routers (DBRs). A xe2x80x9cJOINxe2x80x9d or xe2x80x9cPRUNExe2x80x9d protocol message includes information which associates a particular UBR with a root of a particular multicast tree. The UBR and DBRs maintain complete routing information for each root of a multicast tree, while all other routers in the network subset (non-border routers) maintain routing information only to destinations within the network subset, including the UBR and DBRs.